这道题像我这样的 dp 蒟蒻都能一眼看出 dp 式:
设 sum 为 c 的前缀和,则有
dp[i]=min{dp[j]+((i−j−1)+(sum[i]−sum[j])−L)2} (0≤j<i)
就可以Θ(n2)解决了 ,开O2骗了70分。
考虑优化,令si=sum[i]+i,则有:
dp[i]=min{dp[j]+(si−sj−1−L)2} (0≤j<i)
将 si−1−L 看作一个整体拆开平方(它们与决策点 j 无关),得到:
dp[i]=min{dp[j]+sj2−2×sj×(si−L−1)}+(si−L−1)2 (0≤j<0)
dp[i]=min{dp[j]+sj2−2sisj+2Lsj+2sj}+(si−L−1)2 (0≤j<0)
然后是斜优的套路,设两个决策点 j,k(j<k) 且 j 优于 k。即:
dp[j]+sj2−2sisj+2Lsj+2sj<dp[k]+sk2−2sisk+2Lsk+2sk
(dp[j]+sj2)−(dp[k]+sk2)+2L(sj−sk)+2(sj−sk)<2si(sj−sk)
注意sj<sk , 移项变号:
sj−sk(dp[j]+sj2)−(dp[k]+sk2)+2(L+1)(sj−sk)>2si
sj−sk(dp[j]+sj2+2sj(L+1))−(dp[k]+sk2+2sk(L+1))>2si
现在就可以维护一个下凸包解决,时间复杂度Θ(n)。
#include <cstdio>
#include <iostream>
using namespace std;
#define LL long long
const int MAXN = 50000;
int n , l , c[ MAXN + 5 ] , Head = 1 , Tail = 0 , Que[ MAXN + 5 ];
LL sum[ MAXN + 5 ] , dp[ MAXN + 5 ];
LL Calc( int i ) {
return sum[ i ] + i;
}
double Slope( int u , int v ) {
return ( ( dp[ u ] + Calc( u ) * Calc( u ) + 2 * Calc( u ) * ( l + 1 ) ) - ( dp[ v ] + Calc( v ) * Calc( v )+ 2 * Calc( v ) * ( l + 1 ) ) ) / ( Calc( u ) - Calc( v ) );
}
int main( ) {
scanf("%d %d",&n,&l);
for( int i = 1 ; i <= n ; i ++ )
scanf("%d",&c[ i ]) , sum[ i ] = sum[ i - 1 ] + c[ i ];
Que[ ++ Tail ] = 0;
for( int i = 1 ; i <= n ; i ++ ) {
while( Head < Tail && Slope( Que[ Head ] , Que[ Head + 1 ] ) < 2 * Calc( i ) ) Head ++;
dp[ i ] = dp[ Que[ Head ] ] + ( Calc( i ) - Calc( Que[ Head ] ) - 1 - l ) * ( Calc( i ) - Calc( Que[ Head ] ) - 1 - l );
while( Head < Tail && Slope( Que[ Tail - 1 ] , Que[ Tail ] ) > Slope( Que[ Tail - 1 ] , i ) ) Tail --;
Que[ ++ Tail ] = i;
}
printf("%lld",dp[ n ]);
return 0;
}